from math import *
import numpy as np

#打开文件
with open("Floyd.txt", "r") as f:  # 打开文件
    data = f.read()  # 读取文件
datalist=data.replace("\n"," ")
datalist=datalist.split(" ")
#获取n和m
n=int(datalist[0])
m=int(datalist[1])
datalist.pop(0)#用完出栈,方便处理
datalist.pop(0)

# 初始化
matrix=[[np.inf for col in range(n)] for row in range(n)]#初始化n*n矩阵所有点点距离为无穷
for i in range(n):
  matrix[i][i]=0#自己到自己为0

#读取序偶序列存入列表
datalist=[datalist[i:i + 3] for i in range(0, len(datalist), n)]
#更新邻接矩阵
for i in range(len(datalist)):
  if datalist[i][0] is not '':
    x=int(datalist[i][0])#元组第一项为x
    y=int(datalist[i][1])#元组第二项为y
    weight=int(datalist[i][2])#权值为第三项
    matrix[x-1][y-1]=weight#更新权值
    matrix[y-1][x-1]=weight

#初始化一个空矩阵用来存放所经过的节点
route = [[0 for i in range(1,12)] for j in range(1,12)]   
for i in range(n):
    for j in range(n):
        route[i][j]=j+1


for p1 in range(1,n):#点1
  for p2 in range(1,n):#点2

    #Floyd算法核心
    for m in range(n):      #i相当于是中间点
        for i in range(n):      #j相当于是起始点
            for j in range(n):      #m相当于是终点
                if (matrix[i][j] > matrix[i][m]+matrix[m][j]):
                    matrix[i][j] = matrix[i][m]+matrix[m][j]
                    route[i][j]=route[i][m]
                else:
                    continue

    if route[p1-1][p2-1]==p2:#无中间点
        print('v_%d'%p1,'到v_%d'%p2,'的路径为：v_%d'%(p1)+'->'+'v_%d'%(p2),":","路程为：",matrix[p1-1][p2-1])
        weight=str(matrix[p1-1][p2-1])
        #写入文件
        f = open('Floyd_Ans.txt', 'a')
        f.write('('+str(p1)+','+str(p2)+','+weight+')'+'='+str(p1)+','+str(p2)+"\n")
        f.close()
    else:#有中间点
        x=route[p1-1][p2-1]
        turning=[x]      #创建一个空列表装载路径中间点
        while (route[x-1][p2-1]!=p2):#循环连接最短路
            x=route[x-1][p2-1]
            turning.append(x)

        print('v_%d'% p1,'到v_%d'%p2,'的路径为:v_%d'%p1,end="")
        for i in turning:
            print('->'+'v_%d'%i,end="")
        print('->'+'v_%d'%(p2),":","路程为:",matrix[p1-1][p2-1])
        weight=str(matrix[p1-1][p2-1])
        #写入
        f = open('Floyd_Ans.txt', 'a')
        f.write('('+str(p1)+','+str(p2)+','+weight+')'+'='+str(p1)+','+str(p2))
        for i in turning:
          f.write(','+str(i))
        f.write('\n')
        f.close()



